It is possible for the users of a database management system to draw inferences from the information that they obtain from the database. The inference process can be harmful if the inferred knowledge is something that the user is not authorized to acquire. That is, a user acquiring information which he is not authorized to know has come to be known as the inference problem in database security. In a multilevel operating environment, the users are cleared at different security levels as they access a multilevel database where the data is classified at different sensitivity levels. A multilevel secure database management system (MLS/DBMS) manages a multilevel database where its users cannot access data to which they are not authorized. Currently available multilevel secure database management systems cannot provide a solution to the inference problem, where users of the system issue multiple requests and consequently infer unauthorized knowledge.
Two distinct approaches to handling the inference problem have been proposed in the past. They are:
(i) Handling of inferences during database design. PA1 (ii) Handling of inferences during query processing. PA1 1. Simple constraints that classify a database, a relation or an attribute; PA1 2. Content-based constraints that classify any part of the database depending on the value of some data; PA1 3. Event-based constraints that classify any part of the database depending on the occurrence of some real-world event; PA1 4. Association-based constraints that classify associations between attributes and relations; PA1 5. Release-based constraints that classify any part of the database depending on the information that has been previously released; PA1 6. Aggregate constraints that classify collections of data; PA1 7. Level-based constraints that classify any part of the database depending on the security level of some data; PA1 8. Fuzzy constraints that assign fuzzy values to their classifications; and PA1 9. Logical constraints that specify implications.
The work reported in Morgenstern, M., May 1987, "Security and Inference in Multilevel Database and Knowledge Base Systems," Proceedings of the ACM SIGMOD Conference, San Francisco, Calif.; Hinke, T., April 1988, "Inference Aggregation Detection in Database Management Systems," Proceedings of the IEEE Symposium on Security and Privacy, Oakland, Calif.; Smith, G., May 1990, "Modelling Security-Relevam Data Semantics," Proceedings of the 1990 IEEE Symposium on Security and Privacy, Oakland, Calif.; and Lunt, T., May 1989, "Inference and Aggregation, Facts and Fallacies," Proceedings of the IEEE Symposium on Security and Privacy, Oakland, Calif. focuses on handling inferences during database design where suggestions for database design tools are given.
In contrast, the work reported in Thuraisingham, B., December 1987, "Security Checking in Relational Database Management Systems Augmented with Inference Engines," Computers and Security, Volume 6, No. 6.; Thuraisingham, B., August 1990, The Use of Conceptual Structures in Handling the Inference Problem, Technical Report M90-55, The MITRE Corporation, Bedford, Mass.; Keefe, T., B. Thuraisingham, and W. Tsai, March 1989, "Secure Query Processing Strategies," IEEE Computer, Volume 22, No. 3, pp. 63-70 focuses on handling inferences during query processing.
Other work on handling the inference problem can be found in Buczkowski, L.J., and Perry, E.L., "Database Inference Controller," Interim Technical Report, Ford Aerospace Corporation, February 1989, where an expert system tool which could be used by the System Security Officer off-line to detect and correct logical inferences is proposed. Rowe, N., February 1989, "Inference Security Analysis Using Resolution Theorem-Proving," Proceedings of the 5th International Conference on Data Engineering, Los Angeles, Calif. investigates the use of Prolog for handling inferences.
In Thuraisingham, B., August 1990, The Use of Conceptual Structures in Handling the Inference Problem, Technical Report M90-55, The MITRE Corporation, Bedford, Mass. various strategies that users could utilize to draw inferences are identified. This set of strategies is more complete than the one proposed in Denning, D.E., et al., "Views as a Mechanism for Classification in Multilevel Secure Database Management Systems," Proceedings of the IEEE Symposium on Security and Privacy, Oakland, Calif. 1986. In Thuraisingham, B., August 1990, The Use of Conceptual Structures in Handling the Inference Problem, Technical Report M90-55, The MITRE Corporation, Bedford, Mass., some preliminary ideas on novel approaches to handling the inference problem are discussed. These include approaches based on mathematical programming, inductive inference, information theory and game theory. Further, in Thuraisingham, B., August 1990, The Use of Conceptual Structures in Handling the Inference Problem. Technical Report M90-55, The MITRE Corporation, Bedford, Mass. complexity of the inference problem is analyzed based on concepts in recursive function theory.
The present application discloses an apparatus and method for designing a multilevel secure database management system that can resolve the inference problem via the effective use of security constraints. In the new system, some security constraints are handled during the query operation, some during the update operation, some during the database design operation. The major advance achieved by the invention disclosed herein over prior art is the use of security constraints in a novel way to handle the inference problem. In addition, prototypes which effectively handle these constraints are also disclosed. Further advances relate to the use of conceptual structures for representing and reasoning about multilevel applications, the development of a logic for secure data/knowledge base management systems and the development of a knowledge base inference controller.